package com.feng.leetcode;

public class Tenth {
    public static void main(String[] args) {
        System.out.println(isMatch("ab",".*.."));
    }

    public static boolean isMatch(String s, String p) {
        int i=0,j=0;
        char[] chars = s.toCharArray();
        char[] pChar = p.toCharArray();
        while (i<s.length()){
            if (j>=p.length()){
                return false;
            }
            if (chars[i] == pChar[j]){
                i++;
                j++;
            }else if (pChar[j] == '.'){
                i++;
                j++;
            }else if (pChar[j] == '*'){
                if (pChar[j-1] ==chars[i] || pChar[j-1] == '.'){
                    i++;
                }else if((j+1) < p.length() && (pChar[j+1] == chars[i] || pChar[j+1] =='.')){
                    j+=2;
                    i++;
                }else{
                    return false;
                }
            }else if ((j+1) < p.length() && pChar[j+1] == '*'){
                j+=2;
            }else {
                return false;
            }
        }
        if (j<p.length() && pChar[j] == '*'){
            j++;
            while (j<p.length()){
                if ((j+1) <p.length() && pChar[j+1] == '*'){
                    j+=2;
                }else if (chars[chars.length-1] == pChar[j]){
                    j+=2;
                }else {
                    return false;
                }
            }
        }else if (j<p.length() && pChar[j] == '.'){
            while (j<p.length()){
                if ((j+1) <p.length() && pChar[j+1] == '*'){
                    j+=2;
                }else {
                    return false;
                }
            }
        }else{
            while (j<p.length()){
                if ((j+1) <p.length() && pChar[j+1] == '*'){
                    j+=2;
                }else {
                    return false;
                }
            }
        }
        return true;

    }
}
